package org.fuyd.algorithm.sort;

/**
 * 练习排序算法
 * 
 * @author 永德
 *
 */
public class Sort {

  /**
   * 私有的默认的构造方法
   */
  private Sort() {
    super();
  }
  
  /**
   * 实例化一个sort类的对象
   */
  private static final Sort instance = new Sort();
  
  /**
   * 供外部访问sort，饿汉单例模式，线程安全
   * @return 实例化一个sort类的对象
   */
  public static Sort getInstance(){
    return instance;
  }

  public static void main(String[] args) {
    int[] a = {26, 12, 68, 35, 5};

    System.out.println("排序之前：");
    for (int i = 0; i < a.length; i++) {
      System.out.print(" " + a[i]);
    }

    // bubbleSort(a);
    // insertSort(a);
    System.out.println("\n排序之后：");
    for (int i = 0; i < a.length; i++) {
      System.out.print(" " + a[i]);
    }
  }

  /**
   * 冒泡排序<br>
   * 
   * 时间复杂度最好的情况为O(n)，最坏的情况为O(n的平方)；空间复杂度O(1)。
   * 
   * @param a 待排序的数组
   */
  public static void bubbleSort(int[] a) {
    for (int i = a.length; i > 0; i--) {
      for (int j = 0; j < i - 1; j++) {
        if (a[j] > a[j + 1]) {
          swap(a, j, j + 1);
        }
      }
    }
  }


  /**
   * 交换数组中的两个值
   * 
   * @param a 数组
   * @param x 第x个数
   * @param y 第y个数
   */
  private static void swap(int[] a, int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
  }

  /**
   * 直接插入排序<br>
   * <b>基本思想： </b>
   * <p>
   * 顺序地把待排序的数据元素按其值大小插入到已排序的数据元素子集合中的适当位置， 子集合的数据元素个数从只有一个数据元素开始逐次增大， 当子集合大小最终和集合大小相等时，排序完毕。
   * </p>
   * <p>
   * 时间复杂度：最好的情况为O(n)，最坏的情况为O(n的平方)；空间复杂度为O(1)。
   * </p>
   * 
   * @param a 待排序的数组
   */
  public static void insertSort(int[] a) {
    int i, j, temp;
    int n = a.length;
    for (i = 0; i < n - 1; i++) {
      // 先将a数组中第（i+1）的值放入临时变量temp中
      temp = a[i + 1];
      // 将i赋值给j
      j = i;
      // 当j>-1并且数组中第j个数据的值大于等于临时变量temp的值时
      while (j > -1 && temp <= a[j]) {
        // 将原数组中第j个数据的值赋值给第（j+1）个数据
        a[j + 1] = a[j];
        j--;
      }
      // 将该数字插入到合适的位置
      a[j + 1] = temp;
    }
  }

  /**
   * 希尔排序<br>
   * <b>基本思想：</b>
   * <p>
   * 把待排序的数据元素分成若干个小组，对同一个小组内的数据元素用直接插入排序；小组的个数逐次减少；当完成了所有的数据元素都在一个小组内的排序后排序过程结束。
   * </p>
   * <p>
   * 希尔排序又称缩小增量排序
   * </p>
   * <p>
   * 若增量取值比较合理，希尔排序的时间复杂度约为O(n(lbn)的平方)；空间复杂度O(1)。
   * </p>
   * 
   * @param a
   * @param d
   * @param numOfD
   */
  public static void shellSort(int[] a, int[] d, int numOfD) {
    int i, j, k, m, span;
    int temp;
    int n = a.length;

    for (m = 0; m < numOfD; m++) {
      span = d[m];
      for (k = 0; k < span; k++) {
        for (i = k; i < n - span; i = i + span) {
          temp = a[i + span];
          j = i;
          while (j > -1 && temp <= a[j]) {
            a[j + span] = a[j];
            j = j - span;
          }
          a[j + span] = temp;
        }
      }
    }
  }
}
